package flare.analytics.graph
{
  import flare.animate.Transitioner;
  import flare.util.Property;
  import flare.vis.data.Data;
  import flare.vis.data.EdgeSprite;
  import flare.vis.data.NodeSprite;
  import flare.vis.operator.Operator;

  /**
   * Calculates the link distance from a source node based on a breadth-first
   * traversal. Link distance is calculated as the smallest number of edges
   * connecting a node to a source node. Any edge weights are ignored, to
   * include weighted edges in the calculation, use the
   * <code>ShortestPaths</code> operator instead.
   * 
   * </p>Nodes are annotated with both the computed distance and the incoming
   * edge in the shortest link distance path to a source node. Edges are
   * annotated with a Boolean value indicating whether or not the edge lies
   * along one of these computed shortest paths.</p>
   */
  public class LinkDistance extends Operator
  {
    private var _d:Property = Property.$("props.distance");
    private var _p:Property = Property.$("props.incoming");
    private var _e:Property = Property.$("props.onpath");
    private var _links:int = NodeSprite.GRAPH_LINKS;

    /** The roots of the breadth-first search. The elements of the array
     *  should either be NodeSprite instances or integer indices into
     *  the node array. */
    public var sources:Array;

    /** The property in which to store the link distance. This property
     *  is used to annotate nodes with the minimum link distance to one of
     *  the source nodes. The default value is "props.distance". */
    public function get distanceField():String
    {
      return _d.name;
    }

    public function set distanceField(f:String):void
    {
      _d = Property.$(f);
    }

    /** The property in which to store incoming edges along a shortest
     *  path. This property is used to annotate nodes with the incoming
     *  along a shortest path from one of the source nodes. By following
     *  sequential incoming edges, one can recreate the shortest path from
     *  the nearest source node. The default value is "props.incoming". */
    public function get incomingField():String
    {
      return _p.name;
    }

    public function set incomingField(f:String):void
    {
      _p = Property.$(f);
    }

    /** The property in which to store a path inclusion flag for edges.
     *  This property is used to mark edges as belonging to one of the
     *  computed shortest paths: <code>true</code> indicates that the edge
     *  participates in a shortest path, <code>false</code> indicates that
     *  the edge does not lie along a shortest path. The default value is
     *  "props.onpath". */
    public function get onpathField():String
    {
      return _p.name;
    }

    public function set onpathField(f:String):void
    {
      _p = Property.$(f);
    }

    /** The link type to consider when calculating link distance. Should
     *  be one of <code>NodeSprite.GRAPH_LINKS</code>,
     *  <code>NodeSprite.IN_LINKS</code>, or
     *  <code>NodeSprite.OUT_LINKS</code>. */
    public function get links():int
    {
      return _links;
    }

    public function set links(linkType:int):void
    {
      if(linkType == NodeSprite.GRAPH_LINKS || linkType == NodeSprite.IN_LINKS || linkType == NodeSprite.OUT_LINKS)
      {
        _links = linkType;
      }

      else
      {
        throw new Error("Unsupported link type: " + linkType);
      }
    }

    // --------------------------------------------------------------------

    /**
     * Creates a new LinkDistance operator.
     * @param sources an Array specifying the roots of the breadth-first
     *  search. The elements of the array should either be
     *  <code>NodeSprite</code> instances or integer indices into the node
     *  array.
     */
    public function LinkDistance(sources:Array = null)
    {
      this.sources = sources;
    }

    /** @inheritDoc */
    public override function operate(t:Transitioner = null):void
    {
      calculate(visualization.data, sources);
    }

    /**
     * Calculates link distances from a set of source nodes for for each
     * node in the graph. Each node in the graph will be annotated with
     * its link distance from the nearest source node.
     * @param data the graph to calculate distances for
     * @param sources one or more source nodes from which to measure the
     *  distance. This input can either be a single node or an array of
     *  nodes. Nodes can be indicated as either a <code>NodeSprite</code>
     *  instance or an integer index into the <code>data.nodes</code>
     *  property.
     */
    public function calculate(data:Data, sources:*):void
    {
      var i:int, n:NodeSprite;
      data.edges.setProperty(_e.name, false);
      data.nodes.visit(function(n:NodeSprite):void
      {
        _d.setValue(n, Number.POSITIVE_INFINITY);
        _p.setValue(n, null);
      });

      // initialize queue
      var roots:Array = sources is Array ? sources as Array : [sources];
      var queue:Array = [];

      for(i = 0; i < roots.length; ++i)
      {
        var r:Object = roots[i];

        if(r is NodeSprite)
        {
          n = NodeSprite(r);
        }

        else if(r is int)
        {
          n = data.nodes[int(r)];
        }
        queue.push(n);
        _d.setValue(n, 0);
      }

      while(queue.length > 0)
      {
        var u:NodeSprite = queue.shift();
        var du:int = _d.getValue(u) + 1;
        u.visitEdges(function(e:EdgeSprite):void
        {
          var v:NodeSprite = e.other(u);
          var d:Number = _d.getValue(v);

          if(!isFinite(d))
          {
            queue.push(v);
            _d.setValue(v, du);
            _p.setValue(v, e);
          }
          else if(d > du)
          {
            _d.setValue(v, du);
            _p.setValue(v, e);
          }
        }, _links);
      }

      data.nodes.visit(function(n:NodeSprite):void
      {
        var e:EdgeSprite = _p.getValue(n);

        if(e)_e.setValue(e, true);
      });
    }
  } // end of class LinkDistance
}